package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript:两个链表的第一个公共结点
 * 输入两个链表，找出它们的第一个公共结点

 * @date: 2021/3/17 22:34
 * @version: 1.0
 */
public class Q36_FindFirstCommonNode {
    public static void main(String[] args) {

    }

    /**
     * 使用一个快指针和一个慢指针同时从首节点出发，快指针一次走两步而慢指针一次走一步，如果两指针相遇则说明有环，否则无环
     * 如果两指针相遇，先将快指针重新指向首节点，然后两指针均一次走一步，再次相遇时的结点就是入环结点
     **/
    public ListNode findFirstCommonNode(ListNode pHead1,ListNode pHead2){
        //若其中一个链表为空则不存在相交问题
        if(pHead1 == null || pHead2 == null){
            return null;
        }
        ListNode ringNode1=ringNode(pHead1);
        ListNode ringNode2=ringNode(pHead2);
        //如果一个有环，另一个无环
        if((ringNode1 == null && ringNode2 != null) ||
                (ringNode1 != null && ringNode2 == null)){
            return null;
        }
        //如果两者都无环，判断是否共用尾结点
        else if(ringNode1 == null && ringNode2 == null){
            return firstCommonNode(pHead1, pHead2, null);
        }
        //如果入环结点相同，那么第一个相交的结点肯定在入环结点之前
        if(ringNode1 == ringNode2){
            return firstCommonNode(pHead1, pHead2, ringNode1);
        }
        //如果入环结点不同，看能否通过ringNode1的后继找到ringNode2
        else{
            ListNode p = ringNode1;
            while(p.next != ringNode1){
                p = p.next;
                if(p == ringNode2){
                    break;
                }
            }
            //如果能找到，那么第一个相交的结点既可以是ringNode1也可以是ringNode2
            return (p == ringNode2) ? ringNode1 : null;
        }
    }
    //查找两链表的第一个公共结点，如果两链表无环，则传入common=null，如果都有环且入环结点相同，那么传入common=入环结点
    public ListNode firstCommonNode(ListNode pHead1, ListNode pHead2, ListNode common){
        ListNode p1 = pHead1, p2 = pHead2;
        int len1 = 1, len2 = 1, gap = 0;
        while(p1.next != common){
            p1 = p1.next;
            len1++;
        }
        while(p2.next != common){
            p2 = p2.next;
            len2++;
        }
        //如果是两个无环链表，要判断一下是否有公共尾结点
        if(common == null && p1 != p2){
            return null;
        }
        gap = len1 > len2 ? len1 - len2 : len2 - len1;
        //p1指向长链表，p2指向短链表
        p1 = len1 > len2 ? pHead1 : pHead2;
        p2 = len1 > len2 ? pHead2 : pHead1;
        while(gap-- > 0){
            p1 = p1.next;
        }
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }


    //判断链表是否有环，没有返回null，有则返回入环结点（整个链表是一个环时入环结点就是头结点）
    public ListNode ringNode(ListNode head){
        if(head == null){
            return null;
        }
        ListNode p1 = head, p2 = head;
        while(p1.next != null && p1.next.next != null){
            p1 = p1.next.next;
            p2 = p2.next;
            if(p1 == p2) break; //fixme，break的话是根据题意来的，是有环，但是要找出来；如果只是判断是否有环的话，直接return true
        }
        //可能有，可能没有
        if(p1.next == null || p1.next.next == null){
            return null;//肯定没有
        }
        //代码至此，代表有环，此时p1=p2就是交点，接下如如何求入环点？
        // 让p1在头结点，p2在相遇点，此时往下一步步走，值相当就是入环点
        p1 = head;
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1 == p2 ? p1 : head;//可能整个链表就是一个环，这时入环结点就是头结点！！！
    }

    public static class ListNode{
        int val;
        ListNode next;
        public void ListNode(int val){
            this.val=val;
        }
    }
}
